Although compression applications employ a wide variety of techniques and have different degrees of complexity, they share some common processes. Typical processes used for data compression include numerical processing, logical processing, source modeling and entropy encoding. These processes depend on the data type, and they may be performed in any order or they may be combined.
Numerical processing, like predictive encoding and linear transforms, is normally used for waveform signals, such as images or audio. Logical processing consists of changing the data to a form more suited for compression, such as run-lengths, zero-trees, set-partitioning information or dictionary entries. The source modeling stage is used to account for variations in the statistical properties of the data. Source modeling is responsible for gathering statistics and identifying data contexts that make the source models more accurate and reliable.
What most compression systems have in common is the fact that the final process is entropy encoding, that is, the process of representing information in the most compact form. Entropy encoding may be responsible for doing most of the compression work, or it may complement what has been accomplished by previous stages.
One method of entropy encoding is arithmetic encoding. Among its most desirable features are the following:
(1) When applied to independent and identically distributed (i.i.d.) sources, the compression of each symbol is provably optimal.
(2) It simplifies automatic modeling of complex sources, yielding near-optimal or significantly unproved compression for sources that are not i.i.d.
(3) It is effective in a wide range of situations and compression ratios. The same arithmetic encoding implementation can effectively code all the diverse data created by the different processes of data compression, such as modeling parameters, transform coefficients, signaling, etc.
(4) Its main process is arithmetic, which is supported with ever-increasing efficiency by all general-purpose or digital signal processors (CPUs, DSPs).
(5) It is suited for use as a “compression black-box” by those that are not encoding experts or do not want to implement the encoding algorithm themselves.
However, the compression of arithmetic coding is sufficient only if the values of the source symbol probabilities that it uses for coding are sufficiently accurate. In real-world applications, the probabilities are not always known ahead of time. Instead, the probabilities are often estimated “on-the-fly”, as symbols are coded. Consequently, arithmetic coding compression efficiency is determined by the efficiency of the mechanism that is used to estimate probabilities.
It would be desirable to use a probability estimation technique with arithmetic coding that is capable of reaching a relatively high level of accuracy in a relatively quick manner.